//------------------------------------------------------------------------------
//  <copyright file="SynchronizationAgent.cs" company="Microsoft Corporation">
// The MIT License (MIT)
// 
// Copyright (c) 2014, Microsoft Corporation
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy
//  of this software and associated documentation files (the "Software"), to deal
//  in the Software without restriction, including without limitation the rights
//  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//  copies of the Software, and to permit persons to whom the Software is
//  furnished to do so, subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in
//  all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//  THE SOFTWARE.
//  </copyright>
//------------------------------------------------------------------------------

namespace Microsoft.Robotics.Runtime
{
    using System;
    using System.Collections.Generic;
    using System.Runtime.Serialization;
    using System.Threading;

    /// <summary>
    /// Agent that performs a synchronized join.
    /// It subscribes to two producers and queues received messages until it can find a correspondent, based on the originating time of the message.
    /// When a match is found, it publishes the two messages as a message tuple. 
    /// If no match is possible (based on the sync tolerance setting), the message is discarded.
    /// The agent is designed to be instantiated from code rather than from a manifest.
    /// Synchronization relies on an AgentMessage property called OriginatingTime. 
    /// This property represents the time when the hardware generated the data (e.g. Kinect depth frame) and needs to be carried from agent message to agent message through the pipeline, 
    /// e.g. the LocalMapAgent and the GlobalMapAgent should have the same originating time as the underlying Kinect frame.
    /// </summary>
    /// <remarks>
    /// Ideally this class would derive twice from ISubscriptionReceiver. 
    /// Unfortunately managed code has an unintuitive restriction on inheriting multiple times from the same generic interface, 
    /// because it can create ambiguity when TInput1 is the same as TInput2. This restriction goes away if a class is used instead (ConsumerProducerAgent in this case). 
    /// </remarks>
    /// <typeparam name="TInput1">The first type of input messages accepted by the agent.</typeparam>
    /// <typeparam name="TInput2">The second type of input messages accepted by the agent.</typeparam>
    internal sealed class SynchronizationAgent<TInput1, TInput2> :
        ConsumerProducerAgent<TInput1, MessageTuple<TInput1, TInput2>>,
        ISubscriptionReceiver<TInput2>
        where TInput1 : AgentMessage
        where TInput2 : AgentMessage
    {
        /// <summary>
        /// The maximum number of messages that can accumulate in a queue before we consider it a bug.
        /// Had to up this number because of a bug, this should eventually get changed back to 1000.
        /// This number needs to be very large for the NavWaypointsFromSlamAgent.
        /// </summary>
        private const int DefaultMaxQueueSize = 40000;

        /// <summary>
        /// The synchronization tolerance, in milliseconds.
        /// </summary>
        private readonly int tolerance;
        
        /// <summary>
        /// The additional producer agent we subscribe to.
        /// </summary>
        private readonly string producerAgentName2;

        /// <summary>
        /// A queue that stores the messages received on the first port.
        /// The messages are removed from the queue when they are matched or are proven to be match-less.
        /// </summary>
        private Queue<TInput1> messageQueue1;

        /// <summary>
        /// A queue that stores the messages received on the second port.
        /// The messages are removed from the queue when they are matched or are proven to be match-less.
        /// </summary>
        private Queue<TInput2> messageQueue2;
        
        /// <summary>
        /// The agent we subscribe to.
        /// </summary>
        private IAgentHost producerAgent2;

        /// <summary>
        /// Gets a value indicating whether the synchronization queues are allowed to overflow (and dump the oldest messages).
        /// This should be false in most cases. Needs to be true if the two producers generate data at widely different frequencies.
        /// </summary>
        private bool allowOverflow;

        /// <summary>
        /// Gets a value indicating whether the synchronization agent should activate/deactivate its producers or not.
        /// Useful for synchronized model agents, since model agents do not activate their producers
        /// </summary>
        private bool disableCascadingActivation;

        /// <summary>
        /// Initializes a new instance of the SynchronizationAgent class.
        /// </summary>
        /// <param name="name">The name of the agent.</param>
        /// <param name="producerAgentName1">The name of the first producer to subscribe to.</param>
        /// <param name="producerAgentName2">The name of the second producer to subscribe to.</param>
        /// <param name="tolerance">THe synchronization tolerance, in ms.</param>
        /// <param name="allowOverflow">
        /// True if synchronization queues are allowed to overflow (and dump the oldest messages). This should be false in most cases.
        /// This is used in cases like metric agents, where ground truth messages are less frequent than slam messages, but they still need to be synchronized.
        /// </param>
        /// <param name="disableCascadingActivation">If true, the sync agent doesn't activate/deactivate its producers. Useful for model agents</param>
        public SynchronizationAgent(string name, string producerAgentName1, string producerAgentName2, int tolerance, bool allowOverflow = false, bool disableCascadingActivation = false)
            : base(name, producerAgentName1)
        {
            this.producerAgentName2 = producerAgentName2;
            this.messageQueue1 = new Queue<TInput1>();
            this.messageQueue2 = new Queue<TInput2>();
            this.tolerance = tolerance;
            this.allowOverflow = allowOverflow;
            this.disableCascadingActivation = disableCascadingActivation;
        }

        /// <summary>
        /// Called after construction, to allow the agent to finish initialization. 
        /// </summary>
        /// <param name="locator">A locator that can be used to find other agents.</param>
        public override void Initialize(AgentLocator locator)
        {
            base.Initialize(locator);
            this.producerAgent2 = locator.GetAgent(this.producerAgentName2);
            this.producerAgent2.Subscribe<TInput2>(this);
        }

        /// <summary>
        /// Called when the agent transitions from inactive to active.
        /// </summary>
        public override void OnActivated()
        {
            if (!this.disableCascadingActivation)
            {
                this.producerAgent2.Activate();
                base.OnActivated();
            }
        }

        /// <summary>
        /// Called when the agent transitions from active to inactive.
        /// </summary>
        public override void OnDeactivated()
        {
            if (!this.disableCascadingActivation)
            {
                this.producerAgent2.Deactivate();
                base.OnDeactivated();
            }

            this.messageQueue1.Clear();
            this.messageQueue2.Clear();
        }

        /// <summary>
        /// Called when a new input message is available. 
        /// </summary>
        /// <param name="message">The new message to receive.</param>
        /// <remarks>
        /// Since the message processing is very short and the intent is to inspect all messages that come in in search of matches, 
        /// this method is marked as blocking (meaning a publisher is blocked if publishing faster than this agent can sustain, which realistically happens only if our thread doesn't get any proc time).
        /// Note that the publisher is still async, and is only blocked if the synchronization agent is running 2 messages behind 
        /// (sync agent is processing one, the receiver has queued another one and the publisher is trying to publish a third one).
        /// </remarks>
        [ReceiverConfiguration(BlockIfFull = true)]
        public override void Receive(TInput1 message)
        {
            Tuple<TInput1, TInput2> tuple = this.FindPairOrEnqueue(message, this.messageQueue1, this.messageQueue2);
            if (tuple != null)
            {
                MessageTuple<TInput1, TInput2> aggregateMessage = new MessageTuple<TInput1, TInput2>(
                    tuple.Item1,
                    tuple.Item2,
                    Math.Min(tuple.Item1.OriginatingTime, tuple.Item2.OriginatingTime));
                this.Publisher.Post(aggregateMessage);
            }
        }

        /// <summary>
        /// Called when a new input message is available.
        /// </summary>
        /// <param name="message">The new message to receive.</param>
        /// <remarks>See the remarks on the other Receive method for why this is marked as blocking.</remarks>
        [ReceiverConfiguration(BlockIfFull = true)]
        public void Receive(TInput2 message)
        {
            Tuple<TInput2, TInput1> tuple = this.FindPairOrEnqueue(message, this.messageQueue2, this.messageQueue1);
            if (tuple != null)
            {
                MessageTuple<TInput1, TInput2> aggregateMessage = new MessageTuple<TInput1, TInput2>(
                    tuple.Item2,
                    tuple.Item1,
                    Math.Min(tuple.Item1.OriginatingTime, tuple.Item2.OriginatingTime));
                this.Publisher.Post(aggregateMessage);
            }
        }

        /// <summary>
        /// Called whenever a message of either type is received.
        /// Walks the other queue in search of a match. If none is found, the message is enqueue (if not too old) or discarded.
        /// </summary>
        /// <typeparam name="T1">The message type.</typeparam>
        /// <typeparam name="T2">The type of messages stored in the second queue.</typeparam>
        /// <param name="message">The message to process.</param>
        /// <param name="queue">The queue in which the message is enqueued if no match is found (and the message is not too old)</param>
        /// <param name="otherQueue">The queue to search for matching messages of the second type.</param>
        /// <returns>A tuple if a match is found, null otherwise</returns>
        private Tuple<T1, T2> FindPairOrEnqueue<T1, T2>(T1 message, Queue<T1> queue, Queue<T2> otherQueue)
            where T1 : AgentMessage
            where T2 : AgentMessage
        {
            T2 possiblePair = null;

            this.ValidateOrder<T1>(message, queue);

            // remove any messages from the other queue that are much older than the message we just got
            long bestDelta = long.MaxValue;
            while (otherQueue.Count > 0)
            {
                long delta = message.OriginatingTime - otherQueue.Peek().OriginatingTime;

                // We don't want to stop the search the moment we cross inside the tolerance braket (i.e. when Abs(delta) < tolerance). 
                // Rather, we want to look for the best fit, as there might be more than one message within the tolerance margin.
                if (delta < -this.tolerance || bestDelta <= Math.Abs(delta))
                {
                    break;
                }

                possiblePair = otherQueue.Dequeue();
                bestDelta = Math.Abs(delta);
            }

            // is the first message left in the other queue a match?
            if (possiblePair != null && bestDelta <= this.tolerance)
            {
                return Tuple.Create(message, possiblePair);
            }

            // no match found, enqueue the message and quit
            queue.Enqueue(message);
            if (queue.Count > DefaultMaxQueueSize)
            {
                if (!this.allowOverflow)
                {
                    // throw to make it easier to catch any sync bugs
                    throw new Exception(string.Format("{0}: Number of unprocessed messages of type {1} is too high.", this.Name, typeof(T1)));
                }

                // remove and throw away the oldest message
                queue.Dequeue();
            }

            return null;
        }

        /// <summary>
        /// Ensures that the message is older than the contents of the queue.
        /// </summary>
        /// <typeparam name="T1">The type of messages in the queue</typeparam>
        /// <param name="message">The new message</param>
        /// <param name="queue">The existing queue of messages</param>
        private void ValidateOrder<T1>(T1 message, Queue<T1> queue) where T1 : AgentMessage
        {
            // assert that messages are ordered
            if (queue.Count > 0)
            {
                T1 previousMessage = queue.Peek();
                if (previousMessage != null)
                {
                    if (previousMessage.OriginatingTime > message.OriginatingTime)
                    {
                        throw new Exception(string.Format("Invalid message ordering. Got {0} after {1}", message.OriginatingTime, previousMessage.OriginatingTime));
                    }
                }
            }
        }
    }
}
